// https://www.lintcode.com/problem/max-area-of-island/

public class Solution {
    /**
     * @param grid: a 2D array
     * @return: the maximum area of an island in the given 2D array
     */
    public int maxAreaOfIsland(int[][] grid) {
        // Write your code here
        int ret = 0;
        if (grid.length > 0) {
            for (int i = 0; i < grid.length; ++i) {
                for (int j = 0; j < grid[0].length; ++j) {
                    if (grid[i][j] == 1) {
                        int area = getArea(grid, i, j, 0);
                        if (area > ret) {
                            ret = area;
                        }
                    }
                }
            }
        }
        return ret;
    }
    
    protected int getArea(int[][] grid, int r, int c, int area) {
        int rows = grid.length, cols = grid[0].length;
        if ((r >= 0) && (r < rows) && (c >= 0) && (c < cols) && (grid[r][c] == 1)) {
            grid[r][c] = 0;
            ++area;
            area = getArea(grid, r - 1, c, area);
            area = getArea(grid, r + 1, c, area);
            area = getArea(grid, r, c - 1, area);
            area = getArea(grid, r, c + 1, area);
        }
        return area;
    }
}